package danran.bfs;

import java.util.*;

/**
 * @Classname InvertTree
 * @Description TODO
 * @Date 2021/8/27 19:08
 * @Created by ASUS
 */
public class InvertTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                4,
                new TreeNode(
                        2,
                        new TreeNode(1, null, null),
                        new TreeNode(3, null, null)
                ),
                new TreeNode(
                        7,
                        new TreeNode(6, null, null),
                        new TreeNode(9, null, null)
                )
        );
        System.out.println(new InvertTree().invertTree(root));
    }


    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                TreeNode t = cur.left;
                cur.left = cur.right;
                cur.right = t;
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }
        return root;
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int dfs(int remain) {
        int res = 0;
        if (remain == 1) res += 1;
        else if (remain == 2) res += 2;
        else if (remain == 3) res += 2;
        else {
            boolean b = map.containsKey(remain - 1);
            boolean b1 = map.containsKey(remain - 3);
            if (b && b1) res += (map.get(remain - 1) + map.get(remain - 3));
            if (!b && b1) res += dfs(remain - 1) + map.get(remain - 3);
            if (b && !b1) res += map.get(remain - 1) + dfs(remain - 3);
            if (!b && !b1) res += dfs(remain - 1) + dfs(remain - 3);
        }
        map.put(remain, res);
        return res;
    }
    Map<Integer, Integer> map = new HashMap<>();
}
